/* Author: DO HOANG HAI
 * Main.java
 *
 * Created on June 4, 2006, 8:59 PM
 *
 * Description: This project demonstrates  how to use quick sort algorithm to sort an one-dimension array
 */

package quick;

import java.util.Scanner;

/**
 *
 * @author hai
 */
public class Main {
    
    private static int[] array={1,4,-2,78,-98,-7};
    private static Scanner reader= new Scanner(System.in);
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        sortData();
        displayResult();
    }
     public static void displayResult(){
        for (int index=0; index<array.length; index++)
            System.out.print("  "+ array[index]);
    }
     public static void sortData(){
        quickSort(array, 0, array.length-1);
     }
     protected static void quickSort(int[] ar, int start, int end){
         if (end<=start) return;
        
         int pivotLoc=partition(ar, start, end);
        
         quickSort(ar, start, pivotLoc-1);
         quickSort(ar, pivotLoc+1, end);
     }
     protected static int partition(int[] a, int start, int end){
        
         int pivot = a[start];        
         int leftWall=start;
       
         for (int i=start+1; i<=end; i++){
             if (a[i]<pivot){
                 leftWall++;
                 
                 swap(a,i, leftWall);
                 
             }
         }
         swap(a, start, leftWall);
         return leftWall;
     }
     public static void swap(int[]a, int i, int j){
        
         int temp =a[i];
         a[i]=a[j];
         a[j]=temp;
        
     }
    
}
